---
title: Graph
slug: /graph
section: Math
---

## Graphs

A powerful and flexible graph data structure implementation for working with connected data. This module provides a complete set of tools for creating, manipulating, and traversing graph structures with support for both directed and undirected weighted edges.

## Overview

The Graph module allows you to:

- Create and manage nodes with custom data
- Connect nodes with weighted, directed or undirected edges
- Position nodes in 2D space for spatial algorithms
- Perform common graph traversal operations like BFS and DFS
- Find optimal paths using Dijkstra's algorithm or A* search

## Basic Usage

### Creating a Graph and working with Nodes and Edges

```ts
import { Graph } from 'excalibur';

// Create an empty graph of strings
const graph = new Graph<string>();

// Add a few nodes with string data
const nodeA = graph.addNode("A");
const nodeB = graph.addNode("B");
const nodeC = graph.addNode("C");

// Connect nodes with bidirectional edges (default)
graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeE);

// Connect nodes in one direction only 
graph.addEdge(nodeA, nodeC, { directed: true });

// Connect nodes with weighted edges
graph.addEdge(nodeA, nodeB, { weight: 5 });

// Use coordinates of parent nodes to dictate weighting
graph.addEdge(nodeA, nodeB, {useEuclidean: true});

// Check if nodes are connected
const connected = graph.areNodesConnected(nodeA, nodeB); // true

// Get neighbors of a node
const neighbors = graph.getNeighbors(nodeA); // [nodeB]

// Delete a node (and its edges)
graph.deleteNode(nodeC);

// Delete an edge
graph.deleteEdge(edges[0]);
```

## Core Concepts

### Node Types

The Graph module supports two node types:

Node: Basic graph node with data

PositionNode: Node with 2D spatial coordinates, uses Excalibur's Native Vector type for position

```ts
// Add positioned nodes, when Vector positions are attached to nodes, it returns a PositionNode
const nodeA = graph.addNode("A", new Vector(0, 0));
const nodeB = graph.addNode("B", new Vector(5, 10));
const nodeC = graph.addNode("C", new Vector(10, 5));
```

### Edge Options

The optional third parameter for creating an Edge has this interface (in principle):

```ts
interface EdgeOptions = {
  weighted: number
  useEuclidean: boolean
  direction: boolean
}
```

It is setup as a discriminated union to allow:

- passing a basic weighted value to an edge
- directing the edge to use the positions of its parent nodes to calculate its weighting
- or use no weighting at all

You cannot pass a weighting parameter and direct the Edge to use Euclidean positions of the nodes, you have to pass one or the other.

### Edge Properties

Edges connect nodes and can have properties:

weight: Numeric value representing distance or cost (default: 0)
directed: Whether the edge is one-way or bidirectional (default: true)
partner: reference to a paired edge if a bidirectional edge was created

```ts
// Connect the nodes
spatialGraph.addEdge(nodeA, nodeB, { weight: 11.2, directed: false }); // Euclidean distance

```

### Graph Traversal

#### Breadth-First Search (BFS)

Explore the graph layer by layer, visiting all direct neighbors before moving deeper:

```ts
// Create and populate your graph first
const visitedNodeIds = graph.bfs(startNode);
```

#### Depth-First Search (DFS)

Explore the graph by moving as far as possible along each branch before backtracking:

```ts
// Create and populate your graph first
const visitedNodeIds = graph.dfs(startNode);
```

### Pathfinding Algorithms

#### Shortest Path and Dijkstra's Algorithm

Find the shortest path between two nodes in a weighted graph:

```ts
// Find shortest path from A to C
const { path, distance } = graph.shortestPathDijkstra(nodeA, nodeC);

// Get full analysis
const dijkstraAnalysis = graph.dijkstra(nodeA);
```

#### A* Algorithm

Find the shortest path using spatial information for better performance:

```ts
const aStarResults = graph.astar(nodeA, nodeB);
```
Returns an object with a list of nodes representing the path, a number representing the number of node steps required, the overall distance traversed, and if any nodes were skipped due to them not being PositionNodes.

## Other Features

### Building a Graph from Data Arrays

For convenience, you can create a graph from arrays of node data:
```ts
// Create a graph with string data nodes
const cities = ["New York", "London", "Tokyo", "Sydney", "Paris"];
const graph = Graph.createGraphFromNodes(cities);
```